/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-25
 * Time: 10:10
 */
import javax.swing.*;
import java.awt.*;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

// 点坐标类
class Point {
    double x, y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return String.format("(%.1f, %.1f)", x, y);
    }
}

// 最近点对计算工具类
class ClosestPointsCalculator {
    // 存储最近的两个点
    public static Point p1 = null;
    public static Point p2 = null;

    // 计算两点欧氏距离
    public static double distance(Point a, Point b) {
        double dx = a.x - b.x;
        double dy = a.y - b.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    // 分治算法找最近点对
    public static double findClosest(List<Point> points) {
        if (points.size() < 2) {
            p1 = p2 = null;
            return Double.POSITIVE_INFINITY;
        }

        // 按x坐标排序
        List<Point> sortedByX = new ArrayList<>(points);
        sortedByX.sort(Comparator.comparingDouble(p -> p.x));

        // 调用递归函数
        double minDist = closestRecursive(sortedByX);
        return minDist;
    }

    private static double closestRecursive(List<Point> points) {
        int n = points.size();
        // 少于3个点直接暴力计算
        if (n <= 3) {
            return bruteForce(points, 0, n - 1);
        }

        // 找中点
        int mid = n / 2;
        Point midPoint = points.get(mid);

        // 拆分左右两部分
        List<Point> left = points.subList(0, mid);
        List<Point> right = points.subList(mid, n);

        // 递归计算左右最小距离
        double leftMin = closestRecursive(left);
        double rightMin = closestRecursive(right);
        double minDist = Math.min(leftMin, rightMin);

        // 收集距离中线小于minDist的点
        List<Point> strip = new ArrayList<>();
        for (Point p : points) {
            if (Math.abs(p.x - midPoint.x) < minDist) {
                strip.add(p);
            }
        }

        // 检查strip中的点对
        double stripMin = checkStrip(strip, minDist);
        return Math.min(minDist, stripMin);
    }

    // 暴力计算小规模点集的最近距离
    private static double bruteForce(List<Point> points, int left, int right) {
        double minDist = Double.POSITIVE_INFINITY;
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                Point a = points.get(i);
                Point b = points.get(j);
                double dist = distance(a, b);
                if (dist < minDist) {
                    minDist = dist;
                    p1 = a;
                    p2 = b;
                }
            }
        }
        return minDist;
    }

    // 检查strip中的点对，更新最近点
    private static double checkStrip(List<Point> strip, double minDist) {
        int n = strip.size();
        double min = minDist;

        // 按y坐标排序
        strip.sort(Comparator.comparingDouble(p -> p.y));

        // 每个点最多比较6个点
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && (strip.get(j).y - strip.get(i).y) < min; j++) {
                Point a = strip.get(i);
                Point b = strip.get(j);
                double dist = distance(a, b);
                if (dist < min) {
                    min = dist;
                    p1 = a;
                    p2 = b;
                }
            }
        }
        return min;
    }
}

// 可视化面板
class DrawingPanel extends JPanel {
    private List<Point> points = new ArrayList<>();
    private boolean showAllLines = false; // 是否显示所有点对连线（调试用）

    public DrawingPanel() {
        // 鼠标点击添加点
        addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                points.add(new Point(e.getX(), e.getY()));
                // 计算最近点对
                ClosestPointsCalculator.findClosest(points);
                repaint(); // 刷新界面
            }
        });

        setBackground(Color.WHITE);
        setPreferredSize(new Dimension(800, 600));
    }

    // 切换是否显示所有点对连线
    public void toggleShowAllLines() {
        showAllLines = !showAllLines;
        repaint();
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        Graphics2D g2 = (Graphics2D) g;
        g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

        // 绘制所有点
        g2.setColor(Color.BLUE);
        for (Point p : points) {
            g2.fillOval((int) p.x - 4, (int) p.y - 4, 8, 8); // 绘制4px半径的点
        }

        // 绘制所有点对连线（可选，点多了会很卡）
        if (showAllLines && points.size() >= 2) {
            g2.setColor(new Color(200, 200, 200, 100)); // 浅灰色半透明
            for (int i = 0; i < points.size(); i++) {
                for (int j = i + 1; j < points.size(); j++) {
                    Point a = points.get(i);
                    Point b = points.get(j);
                    g2.drawLine((int) a.x, (int) a.y, (int) b.x, (int) b.y);
                }
            }
        }

        // 绘制最近点对连线
        Point p1 = ClosestPointsCalculator.p1;
        Point p2 = ClosestPointsCalculator.p2;
        if (p1 != null && p2 != null) {
            g2.setColor(Color.RED);
            g2.setStroke(new BasicStroke(2)); // 粗线
            g2.drawLine((int) p1.x, (int) p1.y, (int) p2.x, (int) p2.y);

            // 显示距离信息
            double dist = ClosestPointsCalculator.distance(p1, p2);
            g2.setColor(Color.BLACK);
            g2.drawString(String.format("最近距离: %.2f", dist), 20, 30);
            g2.drawString("点对: " + p1 + " - " + p2, 20, 50);
        } else if (points.size() < 2) {
            g2.drawString("请点击面板添加点（至少2个）", 20, 30);
        }
    }
}

// 主窗口
public class ClosestPointsVisualizer extends JFrame {
    public ClosestPointsVisualizer() {
        setTitle("最近点对问题可视化");
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // 创建面板
        DrawingPanel drawingPanel = new DrawingPanel();

        // 控制按钮
        JPanel controlPanel = new JPanel();
        JButton toggleLinesBtn = new JButton("显示/隐藏所有连线");
        toggleLinesBtn.addActionListener(e -> drawingPanel.toggleShowAllLines());
        controlPanel.add(toggleLinesBtn);

        // 组装界面
        getContentPane().add(drawingPanel, BorderLayout.CENTER);
        getContentPane().add(controlPanel, BorderLayout.SOUTH);

        pack();
        setLocationRelativeTo(null); // 居中显示
        setVisible(true);
    }

    public static void main(String[] args) {
        // 确保UI在事件调度线程中创建
        SwingUtilities.invokeLater(ClosestPointsVisualizer::new);
    }
}